on stage.

he initialisation stage

tialisation step, each cell for an identical pair of residues from

ences is filled by one and others are filled by zeros. Shown in

6 is an example for aligning two sequences x=CAGGCA and

A, where the initialisation stage has been completed.

The initialisation of a Needleman-Wunsch algorithm for aligning CAGGCA and

1

2

3

4

5

A

G

T

C

A

1

C

0

0

0

1

0

2

A

1

0

0

0

1

3

G

0

1

0

0

0

4

G

0

1

0

0

0

5

C

0

0

0

1

0

6

A

1

0

0

0

1

he forward propagation stage

ward propagation process, the cells of the table are filled row by

the bottom to the top of a table and column by column from the

he left of a table. The score calculation rule of the Needleman-

algorithm is defined as below,

ܯ௜௝ൌݏ௜௝൅max൛ܯ௜ାଵ,௝ାଵ, ܯ௜ାଵ,௝ା௞, ܯ௜ା௥,௝ାଵൟ

(7.11)

nd j represent the i^th row and the j^th column, ܯ௜௝ is the alignment

the cell indexed by i and j, ݏ௜௝ is the match score of the cell

by i and j. This update rule indicates that a new alignment score

ised between three scores calculated from three directions as well.

o the Sellers algorithm, they are the diagonal move, the vertical

d the horizontal move. ݏ௜௝൅ܯ௜ାଵ,௝ାଵ is the diagonal move,

ାଵ,௝ାଵ ^{is the partial alignment score of the cell one row below}

column on the right side of the current cell. ݏ௜௝൅ܯ௜ା௥,௝ାଵ is the